package pers.cz.search;

import pers.cz.holder.Holder;

import java.io.Serializable;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 字典树，用于模糊查询
 * @program: PostGirl-panent
 * @description: Trie
 * @author: Cheng Zhi
 * @create: 2021-07-10 12:36
 **/
public class Trie implements Serializable {

    public static Trie trie;
    public static TrieNode root ;

    public Trie() {
        if (root == null) {
            root = new TrieNode();
        }
    }

    public static Trie getTrie() {
        if (trie == null) {
            trie = new Trie();
        }
        return trie;
    }

    static class TrieNode {

        // 标识是否为终节点
        Boolean isEnd;
        // 多少个路线通过该节点
        Integer num;
        // 保存所有儿子节点
        Map<String,TrieNode> sonMap;
        // 标记是否存在儿子节点
        Boolean hasSon;

        TrieNode() {
            isEnd = false;
            hasSon = false;
            num = 1;
            sonMap = new HashMap<String, TrieNode>();
        }
    }

    /**
     * 插入字典树
     * @param sentence
     */
    public void insert(String sentence) {

        TrieNode node = root;

        for (int i=0; i<sentence.length(); i++) {
            String word = String.valueOf(sentence.charAt(i));
            // 如果树中不存在该字
            if (!node.sonMap.containsKey(word)) {
                node.sonMap.put(word,new TrieNode());
                node.hasSon = true;
            } else {
                node.num ++;
            }
            node = node.sonMap.get(word);
        }
        node.isEnd = true;

    }

    /**
     * 在树中查找
     * @param sentence
     * @return
     */
    public boolean search(String sentence) {

        TrieNode node = root;
        for (int i=0; i<sentence.length(); i++) {
            String word = String.valueOf(sentence.charAt(i));
            if (node.sonMap.containsKey(word)) {
                node = node.sonMap.get(word);
            } else {
                return false;
            }
        }

        return node.isEnd;
    }

    /**
     * 获取所有以入参关键字开头的词汇
     * @param sentence
     * @return
     */
    public List<String> searchList(String sentence) {

        List<String> resultList = new ArrayList<>();
        TrieNode node = root;
        StringBuilder prefix = new StringBuilder();
        String[] strings = new String[20];
        int index = 0;
        Holder<Integer> holder = new Holder<>(index);
        for (int i=0; i<sentence.length(); i++) {
            String word = String.valueOf(sentence.charAt(i));

            // 如果树中不包含关键字，直接返回
            if (!node.sonMap.containsKey(word)) {
                return resultList;
            } else {
                node = node.sonMap.get(word);
            }
            prefix.append(word);
            // 判断如果是一句话中的最后一个字符
            if (i == sentence.length() -1) {
                if (node.isEnd) {
                    resultList.add(prefix.toString());
                }
                final String finalSb = prefix.toString();
                recursion(node, resultList, holder, prefix.toString());
            }
        }
        return resultList;
    }

    /**
     * 递归获取字典树的树枝。
     * @param node
     * @return
     */
    private String recursion(TrieNode node, List<String> strings, Holder<Integer> holder, String sb) {

        String prefix = sb;

        if (node.hasSon) {
            for (String key : node.sonMap.keySet()) {
                if (node.sonMap.get(key).isEnd) {
                    //strings[holder.getValue()] = sb+key;
                    strings.add(sb+key);
                }
                holder.setValue(holder.getValue() + 1);
            }
            for (String key : node.sonMap.keySet()) {
                holder.setValue(holder.getValue() + 1);
                recursion(node.sonMap.get(key),strings,holder, sb+key);
            }
        }
        return sb.toString();
    }

    /**
     * 为Trie内部类TrieNode初始化值
     * @param jsonObject
     * @return
     */
/*    public Trie setTrieNode(String jsonObject) {
        TrieNode trieNode = mapToObject(jsonToMap(jsonObject));
        Trie trie = getTrie();
        trie.root = trieNode;

        return trie;
    }*/

    /**
     * 将json转化为Map
     * @param jsonStr
     * @return
     */
/*    public Map<?, ?> jsonToMap(String jsonStr) {
        Map<?, ?> ObjectMap = null;
        Gson gson = new Gson();
        java.lang.reflect.Type type = new com.google.gson.reflect.TypeToken<Map<?,?>>() {}.getType();
        ObjectMap = gson.fromJson(jsonStr, type);
        return ObjectMap;
    }*/

    /**
     * 将map转化为java对象
     * @param map
     * @return
     */
    public TrieNode mapToObject(Map<?, ?> map) {

        TrieNode trieNode = new TrieNode();
        Double doubleNum = (Double) map.get("num");
        trieNode.num = doubleNum.intValue();;
        trieNode.isEnd = (Boolean) map.get("isEnd");
        trieNode.hasSon = (Boolean) map.get("hasSon");
        Map<?,?> sonMap = (Map<?, ?>) map.get("sonMap");
        Map<String, TrieNode> newMap = new HashMap<>();
        for (Object key : sonMap.keySet()) {
            newMap.put((String) key, mapToObject((Map<?, ?>) sonMap.get(key)));
        }
        trieNode.sonMap = newMap;
        return trieNode;
    }

    public static void main(String[] args) {
       Trie chTrie = new Trie();
        String str = "这是,这是一坨,这是,这是一箱,测试,这是个好孩子,这测试,这是行,这是好,这是啥,这是朱,这是猪啊啊啊啊啊啊啊啊";
        String[] splits = str.split(",");
        for (String split : splits) {
            chTrie.insert(split);
        }

        String strs = "这";
        System.out.println(chTrie.searchList(strs));

/*        Map map = chTrie.jsonToMap("{\"Response\":{\"ErrorInfo\":{\"Code\":\"0000\",\"Hint\":\"成功\",\"Message\":\"成功\"},\"RetInfo\":{\"rspCode\":\"00\",\"rspData\":[{\"freeResItems\":[{\"expireTime\":20201001000000,\"freeResType\":10,\"usageDetails\":[{\"freeResUsed\":12345,\"phoneId\":13764337517},{\"freeResUsed\":89877,\"phoneId\":18800270337}],\"validTime\":20201001000000,\"usageTotal\":{\"freeResUsed\":99999,\"freeResRemained\":110,\"freeResTotal\":1231223232},\"freeResItemID\":66661030,\"measureId\":103}],\"productInstance\":130003688482942,\"phoneId\":18800270336,\"productId\":50001014}],\"rspDesc\":\"成功\"}}}");

        String a = "{\"Response\":{\"ErrorInfo\":{\"Code\":\"0000\",\"Hint\":\"成功\",\"Message\":\"成功\"},\"RetInfo\":{\"rspCode\":\"00\",\"rspData\":[{\"freeResItems\":[{\"expireTime\":20201001000000,\"freeResType\":10,\"usageDetails\":[{\"freeResUsed\":12345,\"phoneId\":13764337517},{\"freeResUsed\":89877,\"phoneId\":18800270337}],\"validTime\":20201001000000,\"usageTotal\":[{\"freeResUsed\":99999,\"freeResRemained\":110,\"freeResTotal\":1231223232}],\"freeResItemID\":66661030,\"measureId\":103}],\"productInstance\":130003688482942,\"phoneId\":18800270336,\"productId\":50001014}],\"rspDesc\":\"成功\"}}}";
        System.out.println(map);*/
    }
}
